Міністерство освіти і науки України Національний університет “Львівська політехніка” Кафедра інформаційних систем та мереж Лабораторна робота №11 на тему Динамічні структури даних Львів 2008 Мета роботи: Вивчити способи створення динамічних структур даних (списків, стеків, дерев, ...) та виконання операцій над ними. 1. Ввести з клавіатури послідовність цілих чисел без знаку та записати у відповідне бінарне дерево їх двійкові коди. Згенерувати ціле випадкове число без знаку та, використовуючи дерево, знайти його двійковий код або вивести повідомлення про відсутність числа у дереві. Текст програми: 1) #include<stdio.h> #include<conio.h> #include<stdlib.h> #include<string.h> #define n 10 struct ttree { char *data; struct ttree *left; struct ttree *right; }; char *bina(int a); struct ttree *addtotree(struct ttree *head); void printtree(struct ttree *head); int findtr(struct ttree *head); char *x; void main() { int i,a; struct ttree *head; randomize(); head=0; for(i=0;i<n;i++) { scanf("%d",&a); x=bina(a); head=addtotree(head); } a=random(20); x=bina(a); printtree(head); if (findtr(head)) printf("\n\nznajdeno:\n%s",x); else printf("\n\nneznajdeno:\n%s",x); getch(); } char *bina(int a) { int i; char *b; b=(char *)calloc(9,1); b[8]=0; for(i=7;i>=0;i--,a/=2) b[i]=a%2+'0'; return b; } struct ttree *addtotree(struct ttree *head) { if(!head) { head=(struct ttree *)malloc(sizeof(struct ttree)); head->left=0; head->right=0; head->data=x; } else { if(strcmp(head->data,x)<0) head->right=addtotree(head->right); if(strcmp(head->data,x)>0) head->left=addtotree(head->left); } return head; } void printtree(struct ttree *head) { if(head != 0) { printtree(head->left); puts(head->data); printtree(head->right); } } int findtr(struct ttree *head) {int a=1; if(!head) return 0; if(strcmp(head->data,x)>0) a=findtr(head->left); if(strcmp(head->data,x)<0) a=findtr(head->right); return a; } Відлагодження програми :